1. Field of the Invention
The present invention relates to an image processing method and apparatus for reducing the number of gradation levels of image data through performing error diffusion processing.
2. Description of the Related Art
For outputting an image with a multiple-level gradation obtained through a computer or an image input device, for example, through an image output device such as a printer with a fewer gradation levels, the number of gradation levels of the image data is required to be reduced. Pseudo halftone representation has been utilized for maintaining the quality of an original image while reducing the number of gradation levels. Among several methods of the pseudo halftone representation, an error diffusion method capable of producing a high-quality image has been widely used for printers that generate two levels of output gradation, for example. The error diffusion method is a method of diffusing a quantization error resulting from a target pixel into input image data of unquantized pixels near the target pixel.
The general principle of the error diffusion method will now be described in detail with reference to Hitoshi Takaie and Mitsuo Yae, xe2x80x98Gradation Conversion Technique of Digital Image Data with Cxe2x80x99, in Interface, August 1993, pp. 158-171.
The error diffusion method is to represent pseudo halftones through modulating quantization errors into high frequencies to be less perceptible considering a characteristic of human visual perception. FIG. 1 is a block diagram of an image processing apparatus for implementing typical error diffusion processing. The image processing apparatus comprises: a subtracter 111 for subtracting output data of a filter 114 described below from input image data x (i, j); a quantizer (shown as Q) 112 for quantizing output data of the subtracter 111 and outputting the result as output image data y (i, j); a subtracter 113 for subtracting output data of the subtracter 111 from output image data y (i, j); and the filter 114 for performing specific filtering on the output data of the subtracter 113 and outputting the result to the subtracter 111. In the drawing, e (i, j) represents a quantization error produced through quantization at the quantizer 112. Therefore the output data of the subtracter 113 is quantization error e(i, j). Coordinates of two directions intersecting each other are represented by xe2x80x98ixe2x80x99 and xe2x80x98jxe2x80x99, respectively. The two directions will be called i direction and j direction, respectively.
The filter 114 is a sort of linear filter. The transfer function thereof is determined to be G (z1, z2). Z1 and z2 are variables in z transformation in i direction and j direction, respectively. The overall configuration of the image processing apparatus shown in FIG. 1 is regarded as a two-dimensional delta-sigma modulation circuit. Therefore expression (1) below is given for the relationship of input and output in the image processing apparatus.
Y(z1, z2)=X(z1, z2)+H(z1, z2) E(z1, z2)xe2x80x83xe2x80x83(1)
In expression (1), Y(z1, z2), X(z1, z2) and E(z1, z2) are values produced through z transformation of y(i, j), x(i, j) and e(i, j), respectively. Transfer function H(z1, z2) of the filter for modulating quantization error E(z1, z2) is given by expression (2) below.
H(z1, z2)=1xe2x88x92G(z1, z2)xe2x80x83xe2x80x83(2)
The transfer function H(z1, z2) represents a high-pass filter of two-dimensional finite impulse response (FIR). The high-pass filter is a filter for modulating quantization errors which determines a modulation characteristic of quantization error E(z1, z2) modulated to a higher frequency. In the following description filters indicated with transfer functions H(z1, z2) and G(z1, z2) are shown as filter H(z1, z2) and filter G(z1, z2), respectively.
G(z1, z2) is given by expression (3) below.
G(z1, z2)=xcexa3xcexa3g(n1, n2) z1xe2x88x92n 1z2xe2x88x92n2xe2x80x83xe2x80x83(3)
The first xcexa3 in expression (3) indicates a sum when n1 is from xe2x88x92N1 to M1. The second xcexa3 in expression (3) indicates a sum when n2 is from xe2x88x92N2 to M2. Each of N1, M1, N2 and M2 is a positive integer. A filter coefficient is given by g(n1, n2) and a target pixel by n1=0 and n2=0.
A typical filters as an example of g(i, j), the coefficient of G(z1, z2), is given by expression (4) below. The * in the expression represents a target pixel where g(0, 0)=0.                               g          ⁡                      (                          i              ,              j                        )                          ⁢                  :                ⁢                              (                                                                                xe2x80x83                                                                                        xe2x80x83                                                                    *                                                  7                                                  5                                                                              3                                                  5                                                  7                                                  5                                                  3                                                                              1                                                  3                                                  5                                                  3                                                  1                                                      )                    /          48                                    (        4        )            
FIG. 2 shows the frequency characteristic of error modulation filter H(z1, z2) using filter G(z1, z2) given by expression (4). A greater absolute value of frequency indicates a higher frequency in FIG. 2. Filter G(z1, z2) and filter H(z1, z2) using filter G(z1, z2) given by expression (4) are called filters of Jarvis, Judice and Ninke (referred to as Jarvis"" filter in the following description).
However, the error diffusion method of related art as described above has the following two problems. The first problem is that generation of dots is long delayed in the rising part of the highlight region (where dots are sparse) while generation of white dots (dot-like portions surrounded by dots where there is no dot) is long delayed in the rising part of the shadow region (where dots are dense). Such a phenomenon is called dot delay phenomenon in the present invention.
The second problem is that dots are missing like tailing in the portion near the interface between the region (the shadow region, for example) other than the highlight region and the highlight region. Similarly, white dots are missing like tailing in the portion near the interface between the region (the highlight region, for example) other than the shadow region and the shadow region. Such a phenomenon is called tailing phenomenon in the present invention.
Reference is now made to FIG. 3 and FIG. 4 for describing a typical example of an image where the above-described dot delay phenomenon and tailing phenomenon occur. FIG. 3 shows the original image. The range of gradation values of the original image is from xe2x80x980xe2x80x99 to xe2x80x98255xe2x80x99. The gradation value is xe2x80x98253xe2x80x99 in the background highlight region and xe2x80x982xe2x80x99 in the rectangular shadow region in the center in the original image. The gradation value of the light oblique line drawn in the bottom right portion of the shadow region is xe2x80x98210xe2x80x99 to xe2x80x98240xe2x80x99 in the original image. FIG. 4 shows the image produced through performing the error diffusion processing on the original image shown in FIG. 3 by the image processing apparatus shown in FIG. 1 so that the gradation levels are reduced to two. A Jarvis"" filter is used as the error modulation filter in the error diffusion processing. The processing is performed from left to right in the primary scanning direction and from top to bottom in the secondary scanning direction.
In the image on which the error diffusion processing has been performed shown in FIG. 4, no dot is generated in the top part and the left part of the background where dots are to be evenly generated. This is the dot delay phenomenon. Since the error diffusion processing has been performed from left to right in the primary scanning direction and from top to bottom in the secondary scanning direction in the example shown in FIG. 4, dot generation is delayed in the top part and the left part and there are regions with no dots. The same applies to the rectangular shadow region in the center where generation of white dots is delayed in the top end part and the left end part. In the example shown in FIG. 4, in particular, no white dot is generated in the region from the top end part and the left end part through the part near the bottom right portion in the shadow region.
In the image shown in FIG. 4, there is a region where dots are missing like tailing in the bottom right part of the rectangular shadow region in the center. This is the tailing phenomenon. Part of the oblique line drawn in the bottom right part of the shadow region is missing in the image shown in FIG. 4, due to the tailing phenomenon.
Such dot delay phenomenon and tailing phenomenon significantly reduce the image quality as shown in FIG. 4.
The cause of the dot delay phenomenon and tailing phenomenon will now be described. The threshold value of the quantizer 112 is xe2x80x98128xe2x80x99 or xe2x80x98127xe2x80x99 when error diffusion processing is performed, using the image processing apparatus shown in FIG. 1, so as to reduce the quantization levels of input image data to two levels of xe2x80x980xe2x80x99 and xe2x80x98255xe2x80x99. The threshold value of the quantizer 112 is xe2x80x98128xe2x80x99 in the following description.
The magnitude (absolute value) of error e(i, j) produced at the quantizer 112 is a value as small as xe2x80x982xe2x80x99 when the gradation value of input image data x(i, j) is xe2x80x982xe2x80x99 as in the shadow region of the original image shown in FIG. 3 or when the gradation value of input image data x(i, j) is xe2x80x98253xe2x80x99 as in the highlight region of the original image. The small error produced at the quantizer 112 is diffused into neighboring pixels in accordance with filter coefficient g(i, j) of expression (4) and further reduced to a smaller value. Such small errors of a number of pixels are accumulated. When the number of accumulated errors exceeds the threshold value xe2x80x98128xe2x80x99 of the quantizer 112 (or reaches xe2x80x98128xe2x80x99 or above), a dot or a white dot first appears Accordingly, the cause of the dot delay phenomenon and the tailing phenomenon may be described as follows.
The cause of the dot delay phenomenon is that it takes a long period of time to accumulate errors so that the errors reaches the threshold value since the quantization error produced in each pixel is small in the highlight region or the shadow region.
The cause of the tailing phenomenon is as follows. Quantization errors accumulated in a specific region remain after processing of the region is completed. If the region shifts to the highlight region or to the shadow region, the quantization error produced in each pixel is small as in the case of the dot delay phenomenon. As a result, it takes a long period of time to cancel out the errors accumulated in the specific region.
As thus described, the cause of the dot delay phenomenon and the tailing phenomenon is the same. That is, the dot delay phenomenon and the tailing phenomenon are two sides of the single problem.
In order to overcome the dot delay phenomenon and the tailing phenomenon described above, the optimized threshold error diffusion method has been proposed, as disclosed in Toshiaki Kakutani xe2x80x98Improved Error Diffusion Method for High Quality Outputxe2x80x99, Society of Photographic Science and Technology of Japan 1997 Annual Meeting Abstract, May 27-28, 1997, pp. 116-119.
The optimized threshold error diffusion method will now be briefly described. In the method attention is focused on the cause of the dot delay phenomenon and the tailing phenomenon described above. For reducing input image data whose gradation values range from xe2x80x980xe2x80x99 to xe2x80x98255xe2x80x99 to data whose quantization levels are two of xe2x80x980xe2x80x99 and xe2x80x98255xe2x80x99, the threshold value of the quantizer is not a fixed value such as xe2x80x98128xe2x80x99 but a value close to the gradation value of the input image data. The period of time in which accumulated errors reach the threshold value is thereby reduced. To be specific, the optimized threshold error diffusion method is the method in which threshold Th of the quantizer is the linear function of input image data x(i, j) as represented by expression (5) below.
Th={x(i, j)xc3x97(nxe2x88x921)+128}/nxe2x80x83xe2x80x83(5)
where n is an integer.
FIG. 5 shows the relationship between the level of input image data and threshold Th where n is xe2x80x9812xe2x80x99.
Referring to FIG. 6 and FIG. 7, comparison is made between the image obtained by the typical error diffusion method and the image obtained by the optimized threshold error diffusion method. FIG. 6 shows the image obtained through reducing the input image data as shown in FIG. 3 to data whose quantization levels are two of xe2x80x980xe2x80x99 and xe2x80x98255xe2x80x99 by the typical error diffusion method wherein the threshold value of the quantizer is xe2x80x98128xe2x80x99. FIG. 7 shows the image obtained through reducing the input image data as shown in FIG. 3 to data whose quantization levels are two of xe2x80x980xe2x80x99 and xe2x80x98255xe2x80x99 by the optimized threshold diffusion method wherein xe2x80x98nxe2x80x99 of expression (5) is xe2x80x9812xe2x80x99. In either case a Jarvis"" filter is used as the error modulation filter.
As shown in FIG. 7, the optimized threshold diffusion method resolves the dot delay phenomenon and the tailing phenomenon.
However, the edge of the rectangular shadow region in the center has jaggies in the image shown in FIG. 7. Since the optimized threshold diffusion method produces jaggies on edges of highlight regions and shadow regions, the method reduces the quality of an artificial image such as a character or a computer graphics image wherein a highlight region and a shadow region are distinct. The method causes a natural image to be blurred as well.
In xe2x80x98Improved Error Diffusion Method for High Quality Outputxe2x80x99 mentioned above, a method is disclosed for optimizing the threshold value for each gradation value, providing a table of the relationship between the gradation values and the threshold values, and determining the threshold value for each gradation value, referring to the table, instead of the method wherein the threshold value of the quantizer is the linear function of input image data. However, although the threshold value is optimized in such a manner for the input image data as shown in FIG. 3, there is little difference between this method and the method wherein the threshold value is the linear function of input image data since the number of gradation values is small.
Since the optimized threshold diffusion method requires to refer to image input data for determining the threshold value of the quantizer, time required for reading data is doubled and processing time is increased.
The foregoing problems apply to mean error minimization, used instead of the error diffusion method, as a method of pseudo halftone representation as well. This is because the mean error minimization method and the error diffusion method are similar in that a quantization error resulting from a target pixel is diffused into input image data of unquantized pixels near the target pixel although the procedural steps of the methods are different from each other.
It is an object of the invention to provide an image processing method and apparatus for maintaining the image quality through simple processing while reducing the number of gradation levels of image data through performing error diffusion processing.
An image processing method of the invention comprises the steps of: quantizing input image data of each of pixels forming entire image data based on at least one threshold value so as to convert the input image data into output image data having any of at least two quantization levels; converting a quantization error resulting from quantizing the input image data of each of the pixels in the step of quantizing into a quantization error within a specific range determined for each of the quantization levels, based on the quantization level after quantization; and diffusing the quantization error obtained through conversion in the step of converting with respect to a targeted one of the pixels, into input image data of unquantized pixels near the target pixel.
An image processing apparatus of the invention comprises: a means for quantizing input image data of each of pixels forming entire image data based on at least one threshold value so as to convert the input image data into output image data having any of at least two quantization levels; a means for converting a quantization error resulting from quantizing the input image data of each of the pixels by the means for quantizing into a quantization error within a specific range determined for each of the quantization levels, based on the quantization level after quantization; and a means for diffusing the quantization error obtained through conversion by the means for converting with respect to a targeted one of the pixels, into input image data of unquantized pixels near the target pixel.
According to the image processing method of the invention, input image data of each of pixels is quantized in the step of quantizing, based on at least one threshold value and converted into output image data having any of at least two quantization levels. A quantization error resulting from quantizing the input image data of each of the pixels in the step of quantizing is converted in the step of converting into a quantization error within a specific range determined for each of the quantization levels, based on the quantization level after quantization. The quantization error obtained through conversion in the step of converting with respect to a targeted one of the pixels is diffused into input image data of unquantized pixels near the target pixel.
According to the image processing apparatus of the invention, input image data of each of pixels is quantized by the means for quantizing, based on at least one threshold value and converted into output image data having any of at least two quantization levels. A quantization error resulting from quantizing the input image data of each of the pixels by the means for quantizing is converted by the means for converting into a quantization error within a specific range determined for each of the quantization levels, based on the quantization level after quantization. The quantization error obtained through conversion by the means for converting with respect to a targeted one of the pixels is diffused into input image data of unquantized pixels near the target pixel.
Other and further objects, features and advantages of the invention will appear more fully from the following description.